public class Main {
    public static void main(String[] args) {
        Main main = new Main();
//        String s="cac";
//        main.findSubstringInWraproundString(s);
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        main.lengthOfLIS(nums);
    }

    //环绕字符串中唯一的子字符串
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        //创建一个大小为26的数组，用于处理返回结果
        int[] hash = new int[26];

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1) + 1 || (s.charAt(i) == 'a' && s.charAt(i - 1) == 'z')) {
                dp[i] += dp[i - 1];
                // hash[s.charAt(i)-'a']=Math.max(dp[i],hash[s.charAt(i)-'a']);
            }
        }
        for (int i = 0; i < n; i++) {
            hash[s.charAt(i) - 'a'] = Math.max(dp[i], hash[s.charAt(i) - 'a']);
        }
        int sum = 0;
        for (int flag : hash) {
            sum = sum + flag;
        }
        return sum;
    }


    //最长递增子序列
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return n == 1 ? 1 : max;
    }

//    public int lengthOfLIS(int[] nums)
// {
//         // 1. 创建 dp 表
//         // 2. 初始化
//         // 3. 填表
//         // 4. 返回值
//
//         int n = nums.length;
//         int[] dp = new int[n];
//         for(int i = 0; i < n; i++) dp[i] = 1;
//
//         int ret = 1;
//         for(int i = 1; i < n; i++)
//             {
//             for(int j = 0; j < i; j++)
//                 if(nums[j] < nums[i])
//                 dp[i] = Math.max(dp[j] + 1, dp[i]);
//             ret = Math.max(ret, dp[i]);
//             }
//         return ret;
//         }

    //摆动序列
    public int wiggleMaxLength(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值

        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for (int i = 0; i < n; i++) g[i] = f[i] = 1;

        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) f[i] = Math.max(g[j] + 1, f[i]);
                else if (nums[j] > nums[i]) g[i] = Math.max(f[j] + 1, g[i]);
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
    public int wiggleMaxLength2(int[] nums) {
        if(nums.length <= 1) return nums.length;
        int res = 1, prediff = 0, curdiff = 0;
        for(int i = 0; i < nums.length - 1; i++){
            curdiff = nums[i + 1] - nums[i];
            if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)){
                res++;
                prediff = curdiff;
            }
        }
        return res;
    }


    //最⻓递增⼦序列的个数
    public int findNumberOfLIS(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值

        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) len[i] = count[i] = 1;

        int retlen = 1, retcount = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 == len[i]) // 计数
                        count[i] += count[j];
                    else if (len[j] + 1 > len[i]) // 重新计数
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if (retlen == len[i]) retcount += count[i];
            else if (retlen < len[i]) // 重新计数
            {
                retlen = len[i];
                retcount = count[i];
            }
        }
        return retcount;
    }
}